import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 手动实现归并排序：先将一个数组分解成单独一个的序列，再将单个序列依次组合到新数组，再将新数组拷贝到原数组
 */
public class MergeSortDemo {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2,0};
        int[] temp = new int[arr.length]; // 归并排序需要额外的空间
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("归并排序后: " + Arrays.toString(arr));
        System.out.println("------------------");

        //测试算法：若处理八千万个排序，需要花费多少时间? 本人电脑：11秒
        //测试算法：若处理八十万个排序，需要花费多少时间? 本人电脑：1秒
        mergeSortTest();
    }

    //测试算法：若处理八千万个排序，需要花费多少时间? 本人电脑：11秒
    //测试算法：若处理八十万个排序，需要花费多少时间? 本人电脑：1秒
    public static void mergeSortTest() {
        int[] arr = new int[80000000];
        //先随机生成一个容量为80000个的数组
        for (int i = 0; i < 80000000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        int[] temp = new int[arr.length]; // 归并排序需要额外的空间
        //创建 格式化日期格式对象：
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy.MM.dd HH:mm:ss");
        //创建当前时间的对象
        Date time1 = new Date();
        //对当前时间进行格式化
        String s1 = sdf.format(time1);
        //打印
        System.out.println("排序前时间：" + s1);
        //进行排序
        mergeSort(arr,0, arr.length - 1, temp);
        //再次创建当前时间对象
        Date time2 = new Date();
        String s2 = sdf.format(time2);
        System.out.println("排序后时间：" + s2);
    }

    /**
     * 将数组分解成多个单独序列的方法
     *
     * @param arr   原始数组
     * @param left  原数组左索引
     * @param right 原数组右索引
     * @param temp  中转数组
     */
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            //创建中间值索引
            int mid = (left + right) / 2;
            //递归向左分解
            mergeSort(arr,left,mid,temp);
            //递归向右分解
            mergeSort(arr,mid + 1,right,temp);
            //合并序列
            merge(arr,left,mid,right,temp);
        }
    }

    /**
     * 单个序列的合并方法
     *
     * @param arr   原数组
     * @param left  原数组的左索引
     * @param mid   原数组的中间索引
     * @param right 原数组的右索引
     * @param temp  中转数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //（一）：先把左右两边(有序)的数据 按照规则填充到temp，直到左右两边的有序序列有一方处理完毕
        int i = left;   //创建一个左边序列的指针
        int j = mid + 1;    //创建一个右边序列的指针，并不是最右边的指针
        int t = 0;  //中转数组的下标值
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {//若左边序列的最小值，小于右边序列的最小值，则将左边序列的最小值，添加到中转数组
                temp[t++] = arr[i++];//添加了数据之后，中转数组的下标后移，以及左边序列的指针后移
            } else {
                //若左边序列的最小值，大于右边序列的最小值，则将右边序列的最小值，添加到中转数组
                temp[t++] = arr[j++];//添加了数据之后，中转数组的下标后移，以及右边序列的指针后移
            }
        }

        //（二）：将有剩余的数组的数据依次加入temp中的尾部
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }

        //（三）：将temp数组重新放到arr，注意：并不是每次拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }
}
